package multithreaddatastructure;

import java.util.concurrent.atomic.AtomicReference;

public class ConcurrentLinkedList<T> {

	class ListNode {
		T data;
		ListNode next;
	}

	private AtomicReference<ListNode> head;
	private AtomicReference<ListNode> tail;

	public ConcurrentLinkedList() {
		ListNode dummy = new ListNode();
		head = new AtomicReference<ListNode>(dummy);// dummy head
		tail = new AtomicReference<ListNode>(dummy);
	}

	public void offer(T data) {
		ListNode newNode = new ListNode();
		newNode.data = data;
		ListNode oldTail;
		do {
			oldTail = tail.get();
		} while (!tail.compareAndSet(oldTail, newNode));
		oldTail.next = newNode;
	}

	public T poll() {
		ListNode oldHead;
		do {
			oldHead = head.get();
			if (oldHead.next == null)
				return null;
		} while (!head.compareAndSet(oldHead, oldHead.next));
		return oldHead.next.data;
	}

	void debug() {
		ListNode cur = head.get().next;
		while (cur != null) {
			System.out.println(cur.data);
			cur = cur.next;
		}
	}

	public static void main(String[] args) {
		ConcurrentLinkedList<Integer> list = new ConcurrentLinkedList<Integer>();
		list.offer(10);
		list.offer(11);
		list.offer(12);
		System.out.println("poll: " + list.poll());
		System.out.println("poll: " + list.poll());
		System.out.println("poll: " + list.poll());
		System.out.println("poll: " + list.poll());
		list.offer(10);
		list.offer(11);
		list.offer(12);
		list.debug();
	}

}
